//方法一：动态规划
//dp[n]，每一个位置存放到达该位置时，还能走的最大步数
    //dp[i] = max(nums[i], dp[i - 1] - 1);
    //如果小于等于0，就返回false
// class Solution {
// public:
//     bool canJump(vector<int>& nums) {
//         int n = nums.size();

//         if (n > 1 && nums[0] == 0)
//             return false;

//         vector<int> dp(n, 0);
//         dp[0] = nums[0];
//         for (int i = 1; i < n - 1; i++)
//         {
//             dp[i] = max(nums[i], dp[i - 1] - 1);

//             if (dp[i] <= 0)
//                 return false;
//         }
//         return true;
//     }
// };

//方法二：贪心
//用“层序遍历”的思想
    //假设当前位置的最大步数为num
    //那么就可以在接下来对num个数中找最大值，也就是下一次可以走的最大步数
    //用left和right维护每一层的区间，maxpos记录下一层的最右端点
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = 0, maxPos = 0;
        while (left <= right)
        {
            if (maxPos >= n - 1)    //如果能到达的最远位置已经在数组最右边，返回true
                return true;

            for (int i = left; i <= right; i++)
                maxPos = max(maxPos, i + nums[i]);

            left = right + 1;
            right = maxPos;
        }

        return false;
    }
};